Hanoï

Lien Moodle : https://moodle.epita.fr/mod/page/view.php?id=104272

Contenu du cours

La légende

A la fin du XIXème siècle, un mathématicien français (E. Lucas, 1883) avait inventé la légende suivante :

Dans le grand temple de Bénarès, sous le dôme qui marque le centre du monde, repose un socle de cuivre équipé de trois aiguilles verticales en diamant de 50 cm de haut. A la création, Dieu enfila 64 plateaux en or pur sur une des aiguilles, le plus grand en bas et les autres de plus en plus petits. C'est la tour de Brahmâ. Les moines doivent continûment déplacer les disques de manière que ceux-ci se retrouvent dans la même configuration sur une autre aiguille. La règle de Brahmâ est simple: un seul disque à la fois et jamais un grand plateau sur un plus petit. Arrivé à ce résultat, le monde tombera en poussière et disparaîtra.

A vous de jouer

Il existe un jeu basé sur cette légende. Le but du jeu est de bouger tous les disques du piquet source vers un nouveau piquet (la destination) en se servant du piquet intermédiaire et en respectant les règles suivantes :

• On ne peut déplacer qu'un disque à la fois.
• On ne peut déplacer un disque qui se trouve sous un autre.
• Un disque ne peut être déposé sur un disque plus petit.

Quel est le nombre minimum de déplacements nécessaires pour bouger une pile de n disques?

Bien sûr, si n = 1, un coup suffit ! Si n = 2, c'est aussi assez facile : On bouge le petit disque en position intermédiaire, puis le grand sur l'endroit final. Enfin, on pose le petit disque sur le grand. Finalement, on a déplacé la pile en 3 coups.

Et si n est plus grand ?

Caml

La fonction à écrire prend en paramètre $n$ le nombre de disques et affiche les déplacements : les piquets seront représentés par les 3 entiers 1, 2 et 3.

Dans la fonction ci-dessous, les paramètres $source$ et $destination$ de la fonction récursive représentent le piquet de départ et celui d'arrivée.

    (* displays moves: source -> destination *)

    let move source destination =
      print_int source ;
      print_string " -> " ;
      print_int destination ;
      print_newline()
    ;;

    let hanoi n =
      let rec play n source destination =
        (* FIXME *)
      in
      if n <= 0 then
        invalid_arg "Hanoi: number of disks invalid"
      else
        play n 1 3

Exemple d'application :

    # hanoi 3 ;;
    1 -> 3
    1 -> 2
    3 -> 2
    1 -> 3
    2 -> 1
    2 -> 3
    1 -> 3
    - : unit = ()